/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 *
 * Date: A  April 2011
 */

#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/global_exit.hh"
#include "cpu/base.hh"

template<class Impl>
GlobalExitP<Impl>::GlobalExitP(DerivEdgeCPUParams *params,
        std::string index_mode)
    : BaseExitPredictor<Impl>(params, "Global"),
      globalCtrBits(params->globalCtrBits),
      globalCtrs(this, (params->bexitTableMode == "AliasFree") ? 
              true : false),
      globalPredictorSize(params->globalPredictorSize),
      globalHistoryBits(params->globalHistoryBits),
      blockShiftAmt(params->blockShiftAmt)
{
    if (params->bexitTableMode == "AliasFree") {
        tableMode = AliasFree;
    } else if (params->bexitTableMode == "Normal") {
        tableMode = Normal;
    } else {
        fatal("Invalid table mode for global exit predictor.\n");
    }

    initVars();

    if (index_mode == "Address") {
        globalIndexMode = Address;
    } else if (index_mode == "AddressAndPath") {
        globalIndexMode = AddressAndPath;
    } else if (index_mode == "AddressAndCPath") {
        globalIndexMode = AddressAndCPath;
    } else if (index_mode == "AddressAndHist") {
        globalIndexMode = AddressAndHist;
    } else if (index_mode == "AddressAndCHist") {
        globalIndexMode = AddressAndCHist;
    } else {
        fatal("Invalid global index mode selected for global exit"
                " predictor\n");
    }

    if (params->bexitGlobalHysteresisMode == "Symmetric") {
        hysteresisMode = Symmetric;
    } else if (params->bexitGlobalHysteresisMode == "Asymmetric") {
        hysteresisMode = Asymmetric;
    } else {
        fatal("Invalid hysteresis mode selected for global exit"
                " predictor\n");
    }
}

template<class Impl>
GlobalExitP<Impl>::~GlobalExitP()
{
    DPRINTF(EdgePredUnit,
            "Global predictor destructed!\n");
}

template<class Impl>
void
GlobalExitP<Impl>::initVars()
{
    if (!isPowerOf2(globalPredictorSize)) {
        fatal("Invalid global predictor size!\n");
    }

    /** Setup the array of counters for the global predictor */
    if (tableMode == Normal) {
        globalCtrs.resize(globalPredictorSize, PredictionTableEntry(this));

        for (int i = 0; i < globalPredictorSize; ++i) {
            globalCtrs[i].hysteresis.setBits(globalCtrBits);
            globalCtrs[i].exitID = 1; // Initial to normal branch
        }
    } 

    /** Clear the global history */
    for (int i = 0; i < Impl::MaxThreads ;++i ) {
	globalHistory[i] = 0;
        pathHistoryTable[i].resize(globalHistoryBits, static_cast<Addr>(0));
    }

    globalPredictorMask = floorPow2(globalPredictorSize) - 1;
    /** Setup the global history mask */
    globalHistoryMask = (ULL(0x1) << globalHistoryBits) - 1;

    globalHistoryFile.resize(Impl::MaxInFlightBlockNum);
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
	globalHistoryFile[i] = 0;
        pathHistoryFile[i].resize(globalHistoryBits, static_cast<Addr>(0));
    }

    DPRINTF(EdgePredUnit, "Global: size: %i, mask: %#x, "
            "counter size: %i, history length: %i, "
            "history mask: %#x.\n",
            globalPredictorSize, globalPredictorMask, 
            globalCtrBits, globalHistoryBits, globalHistoryMask);

    threshold = (ULL(0x1) << (globalCtrBits - 1)) - 1;
    threshold = threshold / 2;

    exitIdBits = floorLog2(TheISA::MaxExitsInBlock);

    exitIdMask = (ULL(0x1) << exitIdBits) - 1;

    DPRINTF(EdgePredUnit, "GlobalExitP: exit id bits: %i"
            " exit id mask: %#x\n",
            exitIdBits, exitIdMask);
}

template<class Impl>
void
GlobalExitP<Impl>::reset()
{
    if (tableMode == Normal) {
        for (int i = 0; i < globalPredictorSize; ++i) {
            globalCtrs[i].hysteresis.reset();
            globalCtrs[i].exitID = 0;
        }
    } else if (tableMode == AliasFree) {
        globalCtrs.clear();
    }
	
    //Clear the global history
    for (int i = 0; i < Impl::MaxThreads ;++i) {
	globalHistory[i] = 0;

        for (int j = 0; j < globalHistoryBits; j++) {
            pathHistoryTable[i][j] = 0;
        }
    }
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum ;++i) {
	globalHistoryFile[i] = 0;

        for (int j = 0; j < globalHistoryBits; j++) {
            pathHistoryFile[i][j] = 0;
        }
    }
}

template<class Impl>
inline
uint64_t
GlobalExitP<Impl>::calcGloPredIdx(Addr &block_addr, uint64_t history,
        uint64_t path_hist)
{
    uint64_t index = ULL(0xffffffffffffffff);
    
    if (globalIndexMode == Address) {

        index = block_addr >> blockShiftAmt;

    } else if (globalIndexMode == AddressAndPath) {

        index = (block_addr >> blockShiftAmt) ^
                (path_hist & globalHistoryMask);

    } else if (globalIndexMode == AddressAndCPath) {

        uint64_t pattern = 0x0;

        if (globalHistoryBits > 1) {
            pattern = bits(path_hist, (globalHistoryBits / 2) - 1, 0);
        }

        index = ((block_addr >> blockShiftAmt) << (globalHistoryBits / 2)) |
            pattern;

    } else if (globalIndexMode == AddressAndHist) {

        index = (history & globalHistoryMask) ^ (block_addr >> blockShiftAmt);

    } else if (globalIndexMode == AddressAndCHist) {

        uint64_t pattern = history & globalHistoryMask;

        index = ((block_addr >> blockShiftAmt) << globalHistoryBits) |
            pattern;

    } else {
        panic("Invalid global index mode selected for tournament exit"
                " predictor\n");
    }

    if (tableMode != AliasFree) {
        index &= globalPredictorMask;
    }

    return index;
}

template<class Impl>
TheISA::ExitID
GlobalExitP<Impl>::lookup(BlockID block_id, BlockID oldest_block_id, 
        Addr &block_addr, int addr_space_ID, ThreadID tid)
{
    uint64_t global_history = 0;
    uint64_t path_history = 0;
    uint64_t global_predictor_idx = 0;
    ExitID global_prediction = TheISA::MaxExitsInBlock;

    uint64_t global_history_new = 0;

    //Get global history
    global_history = globalHistory[tid] & globalHistoryMask;
    path_history = getPathHistory(tid);

    global_predictor_idx = calcGloPredIdx(block_addr, global_history,
            path_history);
    
    //Lookup in the global predictor to get its branch prediction
    global_prediction = globalCtrs[global_predictor_idx].exitID;

    DPRINTF(EdgePredUnit,"Global: prediction = %i,"
            " for %#x.\n",
            global_prediction, block_addr);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    // Speculative update
    globalHistoryFile[index] = global_history;

    global_history_new = ((global_history << exitIdBits) |
            (global_prediction & exitIdMask)) &
            globalHistoryMask;

    globalHistory[tid] = global_history_new;

    PathHistory path = pathHistoryTable[tid];
    pathHistoryFile[index] = pathHistoryTable[tid];
    updatePathHistory(path, block_addr);
    pathHistoryTable[tid] = path;

    return global_prediction;
}

template<class Impl>
TheISA::ExitID
GlobalExitP<Impl>::update(BlockID block_id, Addr &block_addr, 
        int addr_space_id, ExitID actual_exit_id, ThreadID tid)
{
    uint64_t global_predictor_hist = 0;
    uint64_t path_hist = 0;
    uint64_t global_predictor_idx = 0;

    assert(actual_exit_id >= 0 && actual_exit_id < TheISA::MaxExitsInBlock);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum -1);

    global_predictor_hist = globalHistoryFile[index] & globalHistoryMask;
    path_hist = getPathHistory(block_id, tid);
        
    global_predictor_idx = calcGloPredIdx(block_addr, global_predictor_hist,
            path_hist);

    ExitID old_pred = globalCtrs[global_predictor_idx].exitID;

    updateHysteresis(globalCtrs[global_predictor_idx], actual_exit_id);

    DPRINTF(EdgePredUnit,"Global: exitID = %i, old pred = %i.\n",
            actual_exit_id,
            old_pred
           );
    return old_pred;
}

template<class Impl>
void
GlobalExitP<Impl>::squash(BlockID block_id, Addr block_pc, 
        ExitID exit_id, ThreadID tid)
{
    uint64_t global_history = 0;
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    // Restore global history to state prior to this branch.
    global_history = globalHistoryFile[index];
    globalHistory[tid] = ((global_history << exitIdBits) | (exit_id & exitIdMask))
        & globalHistoryMask;

    PathHistory path = pathHistoryFile[index];
    updatePathHistory(path, block_pc);
    pathHistoryTable[tid] = path;

    DPRINTF(EdgePredUnit,"Global: Squashing BP to Block [bid:%i]"
            " due to misprediction.\n",
            block_id);
}

template<class Impl>
void
GlobalExitP<Impl>::squash(BlockID block_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);
    uint64_t global_history = 0;

    global_history = globalHistoryFile[index] & globalHistoryMask;
    globalHistory[tid] = global_history;
    pathHistoryTable[tid] = pathHistoryFile[index];

    DPRINTF(EdgePredUnit,"Global: Squashing BP to Block [bid:%i]"
            " due to fault.\n",
            block_id);
}

template<class Impl>
void 
GlobalExitP<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc)
{
    DPRINTF(EdgePredUnit, "Update path history,"
            " Pop: %#x; Push: %#x\n",
            path_history.back(),
            new_pc);

    path_history.pop_back();

    new_pc >>= blockShiftAmt;

    path_history.push_front(new_pc);
}

template<class Impl>
uint64_t
GlobalExitP<Impl>::getPathHistory(BlockID block_id, ThreadID tid)
{
    int speculative_frame = block_id & (Impl::MaxInFlightBlockNum - 1);

    PathHistory path = pathHistoryFile[speculative_frame];
    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
GlobalExitP<Impl>::getPathHistory(ThreadID tid)
{
    PathHistory path = pathHistoryTable[tid];
    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
void
GlobalExitP<Impl>::updateHysteresis(PredictionTableEntry &entry,
        ExitID actual_exit_id)
{
    assert(actual_exit_id >= 0 && actual_exit_id < TheISA::MaxExitsInBlock);

    ExitID current_exit_id = entry.exitID;

    if (hysteresisMode == Symmetric) {
        if (entry.hysteresis.read() <= threshold) {
            entry.exitID = actual_exit_id;
        }

        if (actual_exit_id == current_exit_id) {
            entry.hysteresis.increment();
        } else {
            entry.hysteresis.decrement();
        }
    } else if (hysteresisMode == Asymmetric) {
//        if (entry.hysteresis.read() <= threshold) {
//            entry.exitID = actual_exit_id;
//        }

//        if (actual_exit_id == current_exit_id) {
//            if (actual_exit_id == TheISA::call ||
//                    actual_exit_id == TheISA::ret) {
//                entry.hysteresis.increment((1 << globalCtrBits) - 1);
//            } else {
//                entry.hysteresis.increment();
//            }
//        } else {
//            if (actual_exit_id == TheISA::call ||
//                    actual_exit_id == TheISA::ret) {
//                entry.hysteresis.decrement((1 << globalCtrBits) - 1);
//            } else {
//                entry.hysteresis.decrement();
//            }
//        }
        panic("Asymmetric mode is not implemented.\n");
    } else {
        panic("Invalid hysteresis mode selected.\n");
    }
}

